# 组合总和： https://leetcode-cn.com/problems/combination-sum/

# 常规写法
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        """
            因为元素可以重复使用，基本上就是全排列了。 每次都可以选择 数组中的任意一个
        """
        rst = []
        candidates.sort()
        def gTargetList(nums, total):
            
            # 如果相等就加入结果列表
            if total == target:
                rst.append(nums[:])
                return 
            if total > target: return 

            for i in range(len(candidates)):
                # 保证顺序取元素，没有 [1, 3] [3, 1]的情况
                if nums and candidates[i] < nums[-1]:
                    continue
                nums.append(candidates[i])
                gTargetList(nums, total + candidates[i])
                nums.pop()

        gTargetList([], 0)
        return rst


# 直接记录当前的下标，下一下标只能取大于等于当前元素的下标
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        """
            因为元素可以重复使用，基本上就是全排列了。 每次都可以选择 数组中的任意一个
            有两个剪枝操作： 
            1. total > target 剪枝
            2. 元素排序，依次向前取，[1, 3] [3, 1] 剪枝掉 [3, 1]的情况
        """
        rst = []
        candidates.sort()
        def gTargetList(nums, total, idx):
            
            # 如果相等就加入结果列表
            if total == target:
                rst.append(nums[:])
                return 
            if total > target: return 

            for i in range(idx, len(candidates)):
                nums.append(candidates[i])
                gTargetList(nums, total + candidates[i], i)
                nums.pop()

        gTargetList([], 0, 0)
        return rst